import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class O32II {
    public static void main(String[] args) {

    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        boolean flag = false;
        if (root==null)
            return new ArrayList<>();
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        List<List<Integer>> re = new ArrayList<>();
        while (list.size()!=0){
            List<Integer> temp = new ArrayList<>();
            List<TreeNode> teNode = new ArrayList<>();
            for (TreeNode treeNode : list) {
                temp.add(treeNode.val);
                if (treeNode.left!=null)
                    teNode.add(treeNode.left);
                if (treeNode.right!=null)
                    teNode.add(treeNode.right);
            }
            list = teNode;
            if (flag)
                Collections.reverse(temp);
            re.add(temp);
            flag = !flag;
        }
        return re;
    }
}
